#include "fib_heap.h"
#include <stdio.h>

fib_heap::fib_heap()
{
    min = new Node;
    min = NULL;
    nodes = 0;
}

int fib_heap:: minimo()
{
    if(min != NULL)
    {
        return min->key;
    }
    else
    {
        return -1;
    }
}

void fib_heap:: Insert(int key)
{
    Node *n = new Node;
    n->parent = NULL;
    n->child = NULL;
    n->mark = false;
    n->visited = false;
    n->brother = n;
    n->sister = n;
    n->degree = 0;
    n->key = key;

    if(min == NULL)
    {
        min = n;
    }
    else
    {
        min->brother->sister = n;
        n->brother = min->brother;
        min->brother = n;
        n->sister = min;

        if(min->key > n->key)
        {
            min = n;
        }
    }

    nodes++;

    // Ahora insertamos este nodo tambien en Node Array
    NodeArray.push_back(n);
}

Node *& fib_heap:: Get_Min()
{
    return min;
}

void fib_heap:: Impr(Node *&actual)
{
    if(min != NULL)
    {
        if(actual != NULL)
        {
            if(!actual->visited)
            {
                cout << actual->key << endl;
                actual->visited = true;
                cout << "hijo" << endl;
                Impr(actual->child);
                cout << "hermano" << endl;
                Impr(actual->brother);
            }
        }
    }else{
        cout << "Empty Fibonacci Heap" << endl;
    }
}

void fib_heap:: Reset(Node *&actual)
{
    if(min != NULL)
    {
        if(actual != NULL)
        {
            if(actual->visited)
            {
                actual->visited = false;
                Reset(actual->child);
                Reset(actual->brother);
            }
        }
    }
}

void fib_heap:: Union(Node *&heap_min, int heap_nodes)
{
    if(min == NULL)
    {
        min = heap_min;
    }
    else
    {
        if(heap_min != NULL)
        {
            Node *aux = new Node;
            aux = NULL;
            aux = heap_min->sister;
            heap_min->sister = min->sister;
            min->sister->brother = heap_min;
            aux->brother = min;
            min->sister = aux;
            if(min->key > heap_min->key)
            {
                min = heap_min;
            }
        }
    }

    nodes+=heap_nodes;
}

int fib_heap:: Get_Nodes()
{
    return nodes;
}

void fib_heap:: Cut_Cascade(Node *&actual)
{
    Node *x = new Node;
    x = NULL;
    x = actual->parent;
    Cut(actual, actual->key);
    if(x != NULL){
        x->degree--;
        if(x->mark)
        {
            Cut_Cascade(x);
        }
        else
        {
            x->mark = true;
        }
    }

    nodes--;
}

void fib_heap:: Insert_Node(Node *&actual)
{
    actual->brother = NULL;
    actual->sister = NULL;
    actual->parent = NULL;
    actual->mark = false;
    actual->visited = false;

    if(min == NULL)
    {
        actual->brother = actual;
        actual->sister = actual;
        min = actual;
    }
    else
    {
        min->brother->sister = actual;
        actual->brother = min->brother;
        min->brother = actual;
        actual->sister = min;
        if(min->key > actual->key)
        {
            min = actual;
        }
    }

    nodes++;
}

void fib_heap:: Cut(Node *&actual, int new_key)
{
    if(actual->parent != NULL && actual->parent->degree > 1 && actual->parent->child == actual)
    {
      actual->parent->child = actual->brother;
    }
    else
    {
        if(actual->parent != NULL && actual->parent->degree == 1)
            actual->parent->child = NULL;
    }

     actual->sister->brother = actual->brother;
     actual->brother->sister = actual->sister;
     Insert_Node(actual);
}

void fib_heap:: Decrease_Key(Node *&actual, int new_key)
{
    if(actual != NULL && min != NULL)
    {
        if(new_key <= actual->key)
        {
            actual->key = new_key;

            if(actual->parent != NULL)
            {
                Node *x = new Node;
                x = NULL;
                x = actual->parent;

                if(actual->key < x->key)
                {
                    Cut(actual, new_key);

                    if(x != NULL)
                    {
                        x->degree--;
                        if(x->mark)
                        {
                            Cut_Cascade(x);
                        }
                        else
                        {
                            x->mark = true;
                        }
                    }

                    nodes--;
                }
            }
            else
            {
                if(min->key > actual->key)
                    min = actual;
            }

        }
    }
}

void fib_heap:: Extract_Min()
{
    if(min != NULL)
    {
        if(min->child != NULL)
        {
            int token = min->child->key;
            Clear(min->child);
            min->child->key = min->key + 1;
            Union(min->child, 0);
            min->child->key = token;
        }

        min->sister->brother = min->brother;
        min->brother->sister = min->sister;
        min->child = NULL;

        if(min != min->brother)
        {
            min = min->brother;
            //free(array);
            //*array = (Node *)calloc((int)(log(nodes)/log((1+sqrt(0.5))/2)), sizeof(Node));

            Consolidate(min);
        }
        else
        {
            min = NULL;
        }

        NodeArray.pop_back();
        nodes--;
    }
}

void fib_heap:: Clear(Node *&actual)
{
    Node *help = actual;
    do
    {
        if(help->parent != NULL)
        {
            help->parent = NULL;
            help->mark = false;
        }

        help = help->brother;
    }
    while (help != actual);
}

void fib_heap:: Heap_Link(Node *&actual, Node *&down)
{
    down->parent = actual;
    down->mark = false;
    down->sister->brother = down->brother;
    down->brother->sister = down->sister;

    if(actual->child != NULL)
    {
        actual->child->brother->sister = down;
        down->brother = actual->child->brother;
        actual->child->brother = down;
        down->sister = actual->child;
    }
    else
    {
        down->brother = down;
        down->sister = down;
        actual->child = down;
    }
    //array[actual->degree] = NULL;
    //actual->degree++;
}

void fib_heap:: Consolidate(Node *&actual)
{
    Node *help = actual;
    Node *array[(int)floor(log(nodes)/log((1+sqrt(5.0))/2))];

    for(int i=0; i<(int)floor(log(nodes)/log((1+sqrt(5.0))/2)); i++)
    {
        array[i] = new Node;
        array[i] = NULL;
    }

    do
    {
        while(array[help->degree] != NULL)
        {
            if(help->key < array[help->degree]->key)
            {
                Heap_Link(help, array[help->degree]);
                array[help->degree] = NULL;
                help->degree++;
            }
            else
            {
                Heap_Link(array[help->degree], help);
                help = array[help->degree];
                array[help->degree] = NULL;
                help->degree++;
            }
        }

        if(help->key <= min->key)
            min = help;

        array[help->degree] = help;
        help = help->brother;
    }
    while(array[help->degree] != help);
}

void fib_heap:: Reset_Level(Node *&actual)
{
    if(min != NULL)
    {
        if(actual->visited)
        {
            actual->visited = false;
            Reset_Level(actual->brother);
        }
    }
}

void fib_heap:: Delete(Node *&actual)
{
    Decrease_Key(actual, -INF);
    Extract_Min();
}

void fib_heap:: Is_Heap(Node *&actual, bool &is)
{
    if(min != NULL && is)
    {
        if(actual != NULL)
        {
            if(!actual->visited)
            {
                if(actual->parent != NULL)
                {
                    if(actual->parent->key > actual->key)
                    {
                        is = false;
                    }
                }
                actual->visited = true;
                Is_Heap(actual->child, is);
                Is_Heap(actual->brother, is);
            }
        }
    }
}
